package nl.rug.jvleusen.datastructurelib.graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import nl.rug.jvleusen.datastructurelib.AbstractWeightedGraph;
import nl.rug.jvleusen.datastructurelib.IGraph;

/**
 * @author Jeroen van Leusen
 * @see AbstractWeightedGraph
 * @see IGraph
 */
public class WeightedDirectionalGraph<E> extends AbstractWeightedGraph<E, WeightedDirectionalGraph.WDVertex<E>> {

    private final List<WDVertex<E>> vertices = new ArrayList<WDVertex<E>>();
    private final List<WDEdge<E>> edges = new ArrayList<WDEdge<E>>();

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean add(E x, E y, int weight) {
        WDVertex<E> vx = getVertex(x);
        WDVertex<E> vy = getVertex(y);

        if (vx == null) {
            vx = new WDVertex<E>(x);
            vertices.add(vx);
        }

        if (vy == null) {
            vy = new WDVertex<E>(y);
            vertices.add(vy);
        }

        WDEdge<E> edge = getEdge(vx, vy);

        if (edge == null) {
            //No edge exists yet, we can make it
            edge = new WDEdge<E>(vx, vy, weight);
            edges.add(edge);
            return true;
        } else {
            return false;
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int getEdgeWeight(E x, E y) {
        WDVertex<E> vx = getVertex(x);
        WDVertex<E> vy = getVertex(y);

        //One of the vertices doesn't exist, so the edge cannot exist.
        if (vx == null || vy == null) {
            return -1;
        }

        WDEdge<E> edge = getEdge(vx, vy);

        if (edge == null) {
            return -1;
        } else {
            return edge.weight;
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean setEdgeWeight(E x, E y, int weight) {
        if (weight < 0) {
            throw new IllegalArgumentException("Negative weight is not supported.");
        }

        WDVertex<E> vx = getVertex(x);
        WDVertex<E> vy = getVertex(y);

        //One of the vertices doesn't exist, so the edge cannot exist.
        if (vx == null || vy == null) {
            return false;
        }

        WDEdge<E> edge = getEdge(vx, vy);

        if (edge != null && edge.weight != weight) {
            edge.weight = weight;
            return true;
        }

        return false;
    }

    @Override
    protected List<WDVertex<E>> getVertices() {
        return vertices;
    }

    @Override
    protected WDVertex<E> getVertex(E data) {
        for (WDVertex<E> v : vertices) {
            if (v.getData().equals(data)) {
                return v;
            }
        }
        return null;
    }

    @Override
    protected List<WDVertex<E>> getNeighbors(WDVertex<E> vertex) {
        List<WDVertex<E>> result = new ArrayList<WDVertex<E>>();
        for (WDEdge<E> edge : edges) {
            if (edge.match(vertex)) {
                result.add(edge.vertex2);
            }
        }
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public boolean adjacent(E x, E y) {
        WDVertex<E> vx = getVertex(x);
        WDVertex<E> vy = getVertex(y);

        //One of the vertices doesn't exist, so the edge cannot exist.
        if (vx == null || vy == null) {
            return false;
        }

        return getEdge(vx, vy) != null;
    }

    /**
     * {@inheritDoc}
     */
    public List<E> neighbors(E x) {
        WDVertex<E> vx = getVertex(x);

        if (vx == null) {
            return null;
        }

        List<E> result = new ArrayList<E>();
        for (WDEdge<E> edge : edges) {
            if (edge.match(vx)) {
                result.add(edge.vertex2.getData());
            }
        }
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public boolean delete(E x, E y) {
        WDVertex<E> vx = getVertex(x);
        WDVertex<E> vy = getVertex(y);

        //One of the vertices doesn't exist, so the edge cannot exist.
        if (vx == null || vy == null) {
            return false;
        }
        WDEdge<E> edge = getEdge(vx, vy);

        if (edge != null) {
            edges.remove(edge);
            edge.cleanUp();
            checkForDeadVertex(vx);
            checkForDeadVertex(vy);
            return true;
        } else {
            return false;
        }
    }

    /**
     * {@inheritDoc}
     */
    public boolean contains(E x) {
        return getVertex(x) != null;
    }

    /**
     * {@inheritDoc}
     */
    public Iterator<E> iterator() {
        return new Iterator<E>() {

            private Iterator<WDVertex<E>> helper = vertices.iterator();

            public boolean hasNext() {
                return helper.hasNext();
            }

            public E next() {
                return helper.next().getData();
            }

            public void remove() {
                throw new UnsupportedOperationException("Graphs do not support deletion by iterator.");
            }
        };
    }

    private WDEdge<E> getEdge(WDVertex<E> vx, WDVertex<E> vy) {
        for (WDEdge<E> edge : edges) {
            if (edge.match(vx, vy)) {
                return edge;
            }
        }
        return null;
    }

    private void checkForDeadVertex(WDVertex<E> vx) {
        if (vx.referenceCount == 0) {
            vertices.remove(vx);
        }
    }

    protected static class WDVertex<E> extends AbstractWeightedGraph.Vertex<E, WeightedDirectionalGraph.WDVertex<E>> {

        private final E data;
        private int referenceCount = 0;

        protected WDVertex(E data) {
            this.data = data;
        }

        @Override
        public E getData() {
            return data;
        }
    }

    protected static class WDEdge<E> {

        private final WDVertex<E> vertex1;
        private final WDVertex<E> vertex2;
        private int weight;

        protected WDEdge(WDVertex<E> vertex1, WDVertex<E> vertex2, int weight) {
            this.vertex1 = vertex1;
            this.vertex1.referenceCount++;
            this.vertex2 = vertex2;
            this.vertex2.referenceCount++;
            this.weight = weight;
        }

        protected void cleanUp() {
            this.vertex1.referenceCount--;
            this.vertex2.referenceCount--;
        }

        protected boolean match(WDVertex<E> v1, WDVertex<E> v2) {
            if (vertex1.equals(v1)) {
                return vertex2.equals(v2);
            }
            return false;
        }

        protected boolean match(WDVertex<E> v) {
            return vertex1.equals(v);
        }
    }
}
